package binarysearch;

import org.junit.Test;

import java.util.Arrays;

public class FindMinimumInRotatedSortedArray153 {
    @Test
    public void test() {
        findMin1(new int[]{2,1});
        findMin1(new int[]{3,4,5,1,2});
        findMin1(new int[]{4,5,6,7,0,1,2});
        findMin1(new int[]{11,13,15,17});

        findMin(new int[]{2,1});
        findMin(new int[]{3,4,5,1,2});
        findMin(new int[]{4,5,6,7,0,1,2});
        findMin(new int[]{11,13,15,17});
    }

    public int findMin(int[] n) {
        int left = 0;
        int right = n.length-1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (n[mid] > n[right]) {
            // if (n[mid] >= n[left]) {
                // 注意这里要以right为基准, 不能以left (特别的, n[mid] >= n[left] 也是错的)
                left = mid + 1;
            } else {
                // 注意这里不是 mid-1, 否则对于 [3, 1, 2] 就不行了
                right = mid;
            }
        }
        System.out.format("nums: %s, min: %d\n", Arrays.toString(n), n[left]);
        return n[left];
    }

    public int findMin1(int[] n) {
        int left = 0;
        int right = n.length-1;
        while (left < right) {
            if (left + 1 == right) {
                // 特殊处理两个的情况
                int min = Math.min(n[left], n[right]);
                System.out.format("nums: %s, min: %d\n", Arrays.toString(n), min);
                return min;
            }
            if (n[left] < n[right]) {
                break;
                //return n[left];
            } else { // left > right
                int mid = (left + right) / 2;
                if (n[mid] > n[left]) {
                    left = mid + 1;
                } else {
                    // 注意这里不是 mid-1, 否则对于 [3, 1, 2] 就不行了
                    right = mid;
                }
            }
        }
        System.out.format("nums: %s, min: %d\n", Arrays.toString(n), n[left]);
        return n[left];
    }
}
